// HeadSort 堆排序
// 逻辑上是堆，实际上是动态数组
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>

typedef int HPDataType;
typedef struct Heap
{
    HPDataType* data;
    int size;
    int Capacity;
}HP;

// 打印数组
void PrintArray(int* arr, int n)
{
    for (int i = 0 ; i < n ; i++){
        printf("%d ", arr[i]);
    }
    putchar('\n');
}

void HPInit(HP* php)
{
    assert(php);

    php->data = NULL;
    php->size = php->Capacity = 0;
}

void HPDestroy(HP* php)
{
    assert(php);

    free(php->data);
    php->data = NULL;
    php->size = php->Capacity = 0;
}

void Swap(HPDataType* px, HPDataType* py)
{
    HPDataType tmp = *px;
    *px = *py;
    *py = tmp;
}

void AdjustUp(HPDataType* data, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0){
        // 如果用parent >= 0来判断，最后会都是0，巧合结束，不采用
        if (data[child] < data[parent]){ // 如果是要建大堆，那么就把小于号换成大于号
            Swap(&data[child], &data[parent]);
            child = parent;
            parent = (parent - 1) / 2;
        }
        else {
            break;
        }
    }
}

// 插入数据后，要调整成小堆，可能会影响祖先
// 用数组方便，因为父子存在数量上的关系
// parent = (child - 1) / 2
// child = parent * 2 + 1 | parent * 2 + 2
void HPPush(HP* php, HPDataType val) // 插入后保持数据成堆
{
    assert(php);

    if (php->size == php->Capacity){
        int newCapacity = php->Capacity == 0 ? 4 : php->Capacity * 2;
        HPDataType* tmp = realloc(php->data, sizeof(HPDataType) * newCapacity);
        if (tmp == NULL){
            printf("realloc fail\n");
            exit(-1);
        }
        else {
            php->Capacity = newCapacity;
            php->data = tmp;
        }
    }

    php->data[php->size] = val;
    php->size++;
    AdjustUp(php->data, php->size - 1);
}

void AdjustDown(HPDataType* data, int n, int parent)
{
    // 假设法选出小的孩子
    // 要求除了祖先，左子树右子树必须得是小堆
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && data[child] > data[child + 1]){ // child + 1 < n是为了防止右孩子越界
            child += 1;
        }
        if (data[child] < data[parent]){
            Swap(&data[child], &data[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else {
            break;
        }
    }
}

void HeapPop(HP* php) // 删除堆顶的数据
{
    // 不可以直接覆盖，时间O（N），且会破坏堆结构
    // 先把顶部和尾部交换一下，把尾部删掉
    // 在这方面左子树右子树不被破坏
    // 这时候进行向下调整算法

    // 小堆，堆顶跟小的孩子比较，否则大孩子上来不满足小堆的定义
    assert(php);
    assert(php->size > 0);

    Swap(&php->data[0], &php->data[php->size - 1]);
    php->size--;

    AdjustDown(php->data, php->size, 0);
}

void HPInitArray(HP* php, HPDataType* data, int n)
{
    assert(php);

    php->data = (HPDataType*)malloc(sizeof(HPDataType) * n);
    if (php->data == NULL){
        perror("malloc fail\n");
        exit(-1);
    }
    else {
        memcpy(php->data, data, sizeof(HPDataType) * n);
        php->Capacity = php->size = n;
    }

    // 建堆,其时间复杂度为O(NlogN)，每一层向上的调整次数不同
    // 次数为sigma[2^(i-1)]*(i-1), i位于[1,h]区间
    // 结果为[2^h]*(h-2)+2,h=logN
    // 不常用，向下调整更常用
    //    for (int i = 0 ; i < php->size ; i++){
    //        AdjustUp(php->data, i);
    //    }

    // 效率更高，二叉树越往下节点越多，向下调整明显次数更少，更快，达到O(N)
    for (int i = (php->size - 2) / 2 ; i >= 0 ; i--){ // 从倒数第一个非叶子节点开始调整
        AdjustDown(php->data, php->size, i);
    }

}

HPDataType HeapTop(HP* php)
{
    assert(php);

    return php->data[0];
}

bool isHPEmpty(HP* php)
{
    assert(php);

    return php->size == 0;
}

// 不推荐
// 1.需要堆的数据结构
// 2.需要空间复杂度O(N)
//void HeapSort(int* a, int n)
//{
//    HP hp;
//    HPInitArray(&hp, a, n);
//
//    int i = 0;
//    while (!isHPEmpty(&hp)){
//        a[i++] = HeapTop(&hp);
//        HeapPop(&hp);
//    }
//
//    HPDestroy(&hp);
//}

// 时间复杂度为O(NlogN)
// N是个数，logN是向下调整
void HeapSort(int* data, int n)
{
    // a数组直接建堆
    // 数组都可以看成二叉树
    // 升序要建大堆，建小堆会破坏结构
    // 注意现在没有堆，无法HPPop
    // 这里不改AdjustDown函数，以降序为例
    // 同样，降序需要建立小堆
    for (int i = (n - 2) / 2 ; i >= 0 ; i--){
        AdjustDown(data, n, i);
    }

    // 小堆建成后，交换头尾，最后一个就已经排好
    // 依此类推
    int end = n - 1;
    while (end > 0){
        Swap(&data[0], &data[end]);
        AdjustDown(data, end, 0);
        end--;
    }
}

// topK经典问题
// 求最大十个数(选最大，建小堆;选最小，建大堆)
// 先建一个十个数据的小堆，接着让后续的数与第一个相比较
// 滚动的思想，快且节省空间
// 空间复杂度很低，为O(K)
// 时间复杂度为K+(N-K)*logK
// 当N远大于K时，时间复杂度为O(N)
void topK(int* arr, int nums, int k)
{
    // 成功建起一个小堆
    for (int i = (k - 2) / 2 ; i >= 0 ; i--){
        AdjustDown(arr, k, i);
    }

    for (int i = k ; i < nums ; i++){
        if (arr[i] > arr[0]){
            arr[0] = arr[i];
            AdjustDown(arr, k, 0);
        }
    }

    printf("以下是数组的最大的前%d个数", k);
    PrintArray(arr, k);
}

int main(void)
{
    int arr[] = {9, 2, 5, 6, 3};
//  topK(arr, sizeof(arr) / sizeof(int), 3);

    HeapSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));

    HP hp;
    HPInitArray(&hp, arr, sizeof(arr) / sizeof(int));
    //    HPInit(&hp);
    //
    //    for (int i = 0 ; i < sizeof(arr) / sizeof(int) ; i++){
    //        HPPush(&hp, arr[i]);
    //    }
    //
    //    while (!isHPEmpty(&hp)) {
    //        printf("%d ", HeapTop(&hp));
    //        HeapPop(&hp);
    //    }
    // printf("%d ", HeapTop(&hp));
    HPDestroy(&hp);

    return 0;
}

























